package org.example;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

public class Test1 {
    //leetcode 496 下一个更大元素II https://leetcode.cn/problems/next-greater-element-i/description/
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Deque<Integer> deque = new ArrayDeque<>();
        deque.add(nums2[0]);
        int n1 = nums2.length, n2 = nums1.length;
        Map<Integer,Integer> hash = new HashMap<>();
        for (int i = 1; i < n1; i++) {
            if (nums2[i] > deque.peekFirst()) {
                while (!deque.isEmpty() && deque.peekFirst() < nums2[i]) {
                    hash.put(deque.removeFirst(),nums2[i]);
                }
            }
            deque.addFirst(nums2[i]);
        }
        int[] ret = new int[n2];
        for (int i = 0; i < n2; i++) {
            if (hash.get(nums1[i]) != null) {
                ret[i] = hash.get(nums1[i]);
            }else {
                ret[i] = -1;
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        Test1 test1 = new Test1();
        int[] nums1 = {4,1,2};
        int[] nums2 = {1,3,4,2};
        test1.nextGreaterElement(nums1,nums2);
        System.out.println(555);
    }
}
